package day27;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/11/27 10:44
 */

import java.util.*;

/**
 * 给你一个链表的头节点 head 。
 * <p>
 * 对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。
 * <p>
 * 返回修改后链表的头节点 head 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：head = [5,2,13,3,8]
 * 输出：[13,8]
 * 解释：需要移除的节点是 5 ，2 和 3 。
 * - 节点 13 在节点 5 右侧。
 * - 节点 13 在节点 2 右侧。
 * - 节点 8 在节点 3 右侧。
 * 示例 2：
 * <p>
 * 输入：head = [1,1,1,1]
 * 输出：[1,1,1,1]
 * 解释：每个节点的值都是 1 ，所以没有需要移除的节点。
 */
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution4 {
    public ListNode removeNodes(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head= head.next;
        }
        int maxNum = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for(int i = list.size()-1;i>=0;i--){
            if(list.get(i)>=maxNum){
                stack.push(list.get(i));
                maxNum = list.get(i);
            }
        }
        ListNode pre = new ListNode();
        ListNode node = new ListNode(stack.pop());
        pre.next = node;
        while (!stack.isEmpty()){
            node.next = new ListNode(stack.pop());
            node = node.next;
        }
        return pre.next;
    }
}
